package 动态规划.状态压缩dp;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/6/19 16:32
 */
public class lc2741特别的排列 {
    /*
     这个有点类似 与 **洛谷的 奖励关 **
     从整体上来看，确实有点类似
     */

    private static final int MOD = 1000000007;

    public int specialPerm(int[] nums) {
//        return solution(nums);
        long ans = 0;
        Integer [][]dp = new Integer[nums.length][1 << nums.length];
        for (int i = 0; i < nums.length; i++) {
            // 这一个 点，可别忘记了！ 这里要对 state 的状态进行变更一下！
            /*
             这里 f（index， state） ： 表示的是上一次 选择 index号 元素的时候， 状态为state的时候， 这个state 表示的
             是已经选择 了 index 号元素 之后 的state， 所以 循环调用的时候， 要像下面这样调用。这是非常关键的一个点！
             */
            ans += recursion(i, 0 | (1 << i), nums,dp);
            ans %= MOD;
        }
        return (int) ans;
    }


    /*
     f(index, state) ： 表示的是 ，在   **上一次** 选择 index 号元素，集合的被挑选的状态 为 state的时候，排列的总数目！

     这个题 ，还是记忆化搜索， 比较直接一些，反而使用 dp 不一定能够写对



     */
    public int recursion(int index, int state, int nums[],Integer dp[][]) {
        if (state == (1 << nums.length) - 1) { // 判断 是否所有元素都参与 排列了， 这种全排列的题 ，还真的是有一些技巧！
            return 1;
        }
        if(dp[index][state] != null){
            return dp[index][state];
        }
        long ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if ((state & (1 << i)) == 0 && (nums[i] % nums[index] == 0 || nums[index] % nums[i] == 0)) { // 表示的当前元素， 还没有参与排列， 可以参与排列
                ans += recursion(i, state | (1 << i), nums,dp);
            }
        }
        return dp[index][state] = (int) (ans % MOD);
    }




    /*
     改下dp， 你发现 无法一步到位， 还是要十分理解  f（） 函数的 含义，
     非常的明白 f（） 函数的含义的话， 解题会更加的轻松一些！

     f(index ,state) , index 的范围 是 0 ~ len - 1
     */


    public int dp(int nums[]) {
        int len = nums.length;
        int fullState = 1 << len;
        int dp[][] = new int[len][1 << len];
        long ans = 0, sum = 0;
        for (int index = 0; index < len; index++) {
            dp[index][(1 << len) - 1] = 1;
            for (int state = 0; state < fullState; state++) {
                if(state == 1 << index){
                    continue;
                }
                for (int i = 0; i < len; i++) {
//                    if(i == index){
//                        continue;
//                    }
                    if ((state & (1 << i)) == 0 && (nums[index] % nums[i] == 0 || nums[i] % nums[index] == 0)) {
                        ans += dp[i][state | (1 << i)];
                    }
                }
                dp[index][state] = (int)(ans % MOD);
            }
        }
        for(int i = 0;i < nums.length;i++){
            sum += dp[i][1 << i];
            sum %= MOD;
        }
        return (int)sum;
    }


    /*
     这个 暴力 递归， 肯定是过不了的！
     但是可以从里面，学到一些 关于排列的一些思维，
     比如： 在 全排列的题目 当中， 参数  index 还有没有必要存在的意义 !
     */
    public int solution(int nums[]) {
//        Arrays.sort(nums);
        boolean used[] = new boolean[nums.length];
        Deque<Integer> path = new ArrayDeque<>(nums.length);

        return function(used, nums, path);
    }

    public int function(boolean used[], int nums[], Deque<Integer> path) {
        if (path.size() == nums.length) {
            return 1;
        }
        long ans = 0;
        for (int i = 0; i < nums.length; i++) {
            /*
             怎么 比较 当前选择的元素， 和上一次的最后的一个元素 是否能 去模
             这才是比较 思考的点！ ， 这里 借助了 path 来快速的 定位到， 上一次 选择的元素
             */
            if (path.size() == 0 || (!used[i] && (nums[i] % path.peekLast() == 0 || path.peekLast() % nums[i] == 0))) {
                used[i] = true;
                path.addLast(nums[i]);
                ans += function(used, nums, path);
                used[i] = false;
                path.removeLast();
            }
        }

        return (int) (ans % MOD);
    }

    @Test
    public void test() {
        int nums[] = {2, 3, 6};
        System.out.println(solution(nums));
        System.out.println(specialPerm(nums));
        System.out.println(dp(nums));
        System.out.println();
    }





    /*
     arignote 的写法！
     */
    public int specialPermN(int[] nums) {
        int dp[][] = new int[1 << nums.length][nums.length], sum = 0;
        for (int i = 0; i < nums.length; i++) {
            dp[1 << i][i] = 1;
        }
        for (int i = 1; i < 1 << nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                for (int k = 0; (i & 1 << j) == 0 && k < nums.length; k++) {
                    if ((i & 1 << k) > 0 && (nums[j] % nums[k] == 0 || nums[k] % nums[j] == 0)) {
                        dp[i | 1 << j][j] = (dp[i | 1 << j][j] + dp[i][k]) % 1000000007;
                    }
                }
            }
        }
        for (int i = 0; i < nums.length; i++) {
            sum = (sum + dp[(1 << nums.length) - 1][i]) % 1000000007;
        }
        return sum;
    }

}
